package algorithm.递归算法.二叉树;

/**
 * @Author: Jun
 * @Date: 2018/9/5 10:20
 */
public class Tree<AnyType extends Comparable<? super AnyType>> {
    private static class BinaryNode<AnyType> {
        AnyType element;
        BinaryNode<AnyType> left;
        BinaryNode<AnyType> right;

        BinaryNode(AnyType theElement) {
            this(theElement, null, null);
        }

        BinaryNode(AnyType theElement, BinaryNode<AnyType> lt, BinaryNode<AnyType> rt) {
            element = theElement;
            left = lt;
            right = rt;
        }
    }

    private BinaryNode<AnyType> root;

    public void insert(AnyType x) {
        root = insert(x, root);
    }

    private BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
        if (t == null) {
            return new BinaryNode<>(x, null, null);
        }
        int compareResult = x.compareTo(t.element);
        if (compareResult < 0) {
            t.left = insert(x, t.left);
        } else if (compareResult > 0) {
            t.right = insert(x, t.right);
        }
        return t;
    }

    public void preOrder(BinaryNode<AnyType> node){
        if(node!=null){
            System.out.println(node.element+"");
            preOrder(node.left);
            preOrder(node.right);
        }
    }
    public void midOrder(BinaryNode<AnyType> node){
        if(node!=null){
            midOrder(node.left);
            System.out.println(node.element+"");
            midOrder(node.right);
        }
    }
    public void posOrder(BinaryNode<AnyType> node){
        if (node!=null){
            posOrder(node.left);
            posOrder(node.right);
            System.out.println(node.element+"");
        }
    }

    /**
     * 层序遍历
     * @param node
     */
    public void levelOrder(BinaryNode<AnyType> node){
        if (node==null){
            return;
        }
        int depth=depth(node);
        for (int i = 1; i <= depth; i++) {
            levelOrder(node,i);
        }
    }

    /**
     *
     * @param node
     * @param level
     */
    public void levelOrder(BinaryNode<AnyType> node,int level){
        if(node==null||level<1){
            return;
        }
        if(level==1){
            System.out.println(node.element+"");
            return;
        }
        levelOrder(node.left,level-1);
        levelOrder(node.right,level-1);
    }

    /**
     * 检查深度
     * @param Node
     * @return
     */
    public int depth(BinaryNode<AnyType> Node) {
        if (Node == null) {
            return 0;
        }

        int l = depth(Node.left);
        int r = depth(Node.right);
        if (l > r) {
            return l + 1;
        } else {
            return r + 1;
        }
    }
    public static void main( String[] args )
    {
        int[] input = {4, 2, 6, 3,1, 5, 7, 8, 10};
        Tree<Integer> tree = new Tree<>();
        for(int i = 0; i < input.length; i++)
        {
            tree.insert(input[i]);
        }
        System.out.print( "前序遍历 ：" );
        tree.preOrder(tree.root);
        System.out.print( "\n中序遍历 ：" );
        tree.midOrder(tree.root);
        System.out.print( "\n后序遍历 ：" );
        tree.posOrder(tree.root);
        System.out.print("\n递归层序遍历：");
        tree.levelOrder(tree.root);
    }
}
